Polygon meshes are widely used in computer aided geometric design, geometric modeling, medical imaging, and computer graphics to represent surfaces in digital form. Polygon meshes are described in detail in U.S. Pat. No. 5,506,947 “Curve and Surface Smoothing Without Shrinkage,” by G. Taubin, and in the paper “A Signal Processing Approach To Fair Surface Design,” by G. Taubin, Siggraph'95 Conference Proceedings, August 1995, pages 351-358, both are incorporated herein by reference in its entirety for all purposes. A polygon mesh includes a polygon mesh connectivity and at least one polygon mesh signal.
A polygon mesh connectivity includes a plurality of polygon mesh vertices, and polygon mesh faces. Each polygon mesh face is a cycle of three or more polygon mesh corners. Each polygon mesh corner corresponds to one of the polygon mesh vertices. Every polygon mesh face is said to be supported by its polygon mesh corners. A polygon mesh edge is an unordered pair of mesh vertices that are consecutive in at least one polygon mesh face, in which case the polygon mesh edge is said to be on the boundary of the polygon mesh face, and to join the two polygon mesh vertices, and the polygon mesh face is said to be incident to the polygon mesh edge. The two polygon mesh vertices are called the ends of the polygon mesh edge. One or more polygon mesh faces may be incident to the same polygon mesh edge. A boundary edge is a polygon mesh edge with exactly one incident polygon mesh face. A regular edge is a polygon mesh edge with exactly two incident polygon mesh faces. A singular edge is a polygon mesh edge with three or more incident polygon mesh faces. The ends of boundary edges are called boundary vertices, and the remaining polygon mesh vertices are called internal vertices. Polygon meshes are well known to those skilled in the prior art.
A graph is composed of a plurality of graph vertices and graph edges, with each graph edge being an unordered pair of graph vertices. Each graph edge is said to connect or to join its two graph vertices, and to be incident to each one of the two graph vertices. Two graph vertices connected by a graph edge are called neighbors. The vertex neighborhood of a graph vertex of a graph is the set of graph vertices of the graph connected to the graph vertex by a graph edge of the graph. A neighbor graph vertex of the graph vertex is a member of the neighborhood of a graph vertex. Graphs are well known to those skilled in the prior art.
The primal graph of a polygon mesh connectivity is a graph with the polygon mesh vertices of the polygon mesh connectivity as primal graph vertices, and the polygon mesh edges of the polygon mesh connectivity as primal graph edges. The dual graph of a polygon mesh connectivity is a graph with the polygon mesh faces of the polygon mesh connectivity as dual graph vertices, and a plurality of dual graph edges. Each dual graph edge corresponds to a particular regular edge of the polygon mesh connectivity, and is composed of the two polygon mesh faces which the regular edge is incident to. The vertex star of a polygon mesh vertex of a polygon mesh is the neighborhood of the polygon mesh vertex in the primal graph of the polygon mesh. The face star of a polygon mesh face of a polygon mesh is the neighborhood of the polygon mesh face in the dual graph of the polygon mesh.
A graph signal on a graph is composed of signal points. Each signal point is a point in a N-dimensional space and corresponds to one of the graph vertices of the graph. The signal points of a graph signal may represent different properties, such as space positions, color vectors, normal vectors, and texture coordinates used to render images of the graph. The signal points of a graph signal may also represent physical properties such as temperature or mechanical strain forces associated with numerical simulations. A spherical graph signal is a graph signal in which all the signal points belong to a N-dimensional sphere of constant radius. A graph signal operator takes an input graph signal as input, and produces an output graph signal on the same graph as output. The value of each output signal point can be a function of zero or more input signal points, and of zero or more operator parameters. Examples of graph signal operators are introduced later in this disclosure.
A polygon mesh signal can be either a primal mesh signal or a dual mesh signal.
A primal mesh signal of a polygon mesh is composed of primal points. Each primal point is a point in a N-dimensional space and corresponds to one of the polygon mesh vertices of the polygon mesh connectivity. The primal points of a primal mesh signal may represent different properties of the polygon mesh, such as vertex positions which define the geometry of the polygon mesh, color vectors, normal vectors, and texture coordinates used to generate pictures of the shape represented by the polygon mesh. The primal points of a primal mesh signal may also represent physical properties such as temperature or mechanical strain forces associated with numerical simulations. In this disclosure the primal mesh signal defined by the vertex positions of a polygon mesh is called the vertex position signal of the polygon mesh. A primal mesh signal is also a graph signal on the primal graph of the polygon mesh connectivity. The vertex position signal of a polygon mesh is a graph signal on the primal graph of the polygon mesh connectivity. In this disclosure, the primal points of a vertex position signal are called vertex positions.
A dual mesh signal of a polygon mesh is composed of dual points. Each dual point is a point in a N-dimensional space and corresponds to one polygon mesh face of the polygon mesh connectivity. The dual points of a dual mesh signal may represent different properties of the polygon mesh, such as face normal vectors which define the orientation of the polygon mesh faces, and color vectors, used to generate pictures of the shape represented by the polygon mesh. A dual mesh signal is also a graph signal on the dual graph of the polygon mesh connectivity. In this disclosure the dual mesh signal defined by the face normal vectors of a polygon mesh is called the face normal signal of the polygon mesh. The face normal signal of the polygon mesh is a spherical graph signal on the dual graph of the polygon mesh connectivity. In this disclosure, the dual points of a face normal signal are called face normals. Sometimes polygon meshes are constructed as the result of measurements performed by a three-dimensional camera, laser scanner, CAT scanner, or other three-dimensional shape measurement device. These polygon meshes approximate the topology and geometry of a physical object, as opposed of a virtual object created in a computer without a physical realization. Data obtained as a result of physical measurements contain noise. Mesh smoothing algorithms are used to remove noise from polygon mesh signals. Mesh smoothing algorithms operate on either primal mesh signals or dual mesh signals. Mesh smoothing algorithms are also referred to herein as mesh smoothing operators. Prior art mesh smoothing algorithms are described in the paper “Linear Anisotropic Mesh Filtering” by Gabriel Taubin, IBM Research Report RC-22213, Oct. 18, 2001, which is here incorporated by reference in its entirety. Mesh smoothing operators are also used as design tools in interactive geometric modeling systems, in conjunction with other mesh operators that modify the topology and/or the geometry of polygon meshes. Amongst these other mesh operators, connectivity refinement schemes based on recursive subdivision are particularly important to design geometric models within a multi-resolution framework. In this context it is important to be able to apply smoothing operators locally, adaptively, and also with more general constraints. In addition to being able to constrain certain vertex positions, it is also desirable to be able to specify the values of some normal vectors, particularly along curves defined by mesh edges. With normal vector constraints surface patches can be joined with tangent plane continuity, and the sharpness of ridge curves embedded in the surfaces can be controlled.
Algorithms with linear time and space complexity are desirable to operate on large data sets, particularly for applications such as surface design and polygon mesh editing, where interactive rates are a primary concern. The simplest polygon mesh smoothing algorithm that satisfies these linear complexity requirements is Laplacian smoothing. Most mesh smoothing algorithms derive from Laplacian smoothing. Laplacian smoothing is a simple and widely used algorithm for denoising polygon mesh signals. It was first introduced to improve the quality of finite element meshes used in engineering applications to perform numerical simulations of physical phenomena. In this context the vertex positions signal of a polygon mesh is two-dimensional, and the polygon mesh connectivity has boundary mesh vertices as well as internal mesh vertices. Vertex positions corresponding to boundary mesh vertices are constrained not to move, but vertex positions corresponding to internal mesh vertices are simultaneously moved to the corresponding output vertex positions computed by a Laplacian smoothing operator. And then the process is iterated a number of times.
A Laplacian operator is a particular type of graph signal operator. When a Laplacian operator is applied to a graph signal, it produces a Laplacian displacement signal. In this disclosure the signal points of the Laplacian displacement signal are called Laplacian displacements. The Laplacian displacement corresponding to a graph vertex is computed as a sum of a plurality of weighted neighbor displacements, with each weighted neighbor displacement corresponding to one neighbor graph vertex of the graph vertex and equal to a neighbor weight multiplied by a neighbor displacement. The neighbor displacement is computed by subtracting the signal point of the vertex graph from the signal point of the neighbor graph vertex. In the prior art the neighbor weights have scalar values. In this disclosure a Laplacian smoothing operator with scalar neighbor weights is called isotropic Laplacian operator. The values for the neighbor weights can be chosen in different ways. One common method used in the prior art is to set each neighbor weight corresponding to a neighbor vertex of a graph vertex equal to the inverse of the number of elements in the vertex neighborhood of the graph vertex. In this disclosure we refer to this particular Laplacian operator as the Laplacian operator with valence weights. This is one example of linear Laplacian operator, where the neighbor weights are not function of the values of the signal points of the graph signal upon which the Laplacian operator is applied. Other linear Laplacian operators have been proposed in the prior art. Examples of linear Laplacian operators, where the weights are chosen to smooth mesh boundaries and to enhance mesh creases, are discussed in the paper “A Signal Processing Approach To Fair Surface Design,” by G. Taubin, Siggraph'95 Conference Proceedings, August 1995, pages 351-358, mentioned above. In a nonlinear Laplacian operator the neighbor weights are computed as function of the values of the signal points of the graph signal upon which the Laplacian operator is applied. Non-linear Laplacian operators have been proposed in the prior art. The main problem with non-linear Laplacian operators is that it is significantly more computationally expensive to evaluate them. It is also more difficult to analyze their behavior because of the non-linearities. Linear and non-linear Laplacian operators are discussed in the paper “Linear Anisotropic Mesh Filtering” by Gabriel Taubin, IBM Research Report RC-22213, Oct. 18, 2001.
A Laplacian smoothing step is a graph signal operator defined by a Laplacian smoothing operator and a smoothing parameter. In the prior art, the smoothing parameter is typically a single number, which is independent of both the graph, and the graph signal upon which the Laplacian operator is applied. The smoothing parameter can also be incorporated by multiplication into the neighbor weights of the Laplacian smoothing operator, in which case the Laplacian smoothing steps is equal to the Laplacian smoothing operators. In some cases it is better to combine the smoothing operator with the neighbor weights, and in other cases it is better to have the smoothing parameter as a separate entity. The smoothing parameter can also be a one-dimensional graph signal on the same graph, with a different value for each graph vertex. The former case, where the smoothing parameter is a single number, can also be regarded as a graph signal, where all the smoothing parameter signal points have the same value. In both cases each output graph signal point corresponding to a vertex graph is computed as the sum of the input signal point corresponding to the same graph vertex plus a scaled displacement. The scale displacement is computed as the product of a smoothing parameter signal point times a Laplacian displacement, with both the smoothing parameter signal point and the Laplacian displacement corresponding to the same graph vertex.
Note that when a Laplacian smoothing step is applied to a graph signal, the result is another graph signal, but when a Laplacian smoothing step is applied to a spherical signal, the result is usually no longer a spherical signal. Laplacian smoothing can be used to smooth the spherical graph signal on the graph to produce a Laplacian graph signal composed of Laplacian signal points. But the resulting Laplacian signal points would no longer be of the same length as the spherical signal points. Each one of the Laplacian signal points can be normalized to the common length of the spherical signal points, if non zero. But there is no guarantee that all the Laplacian signal points will be non-zero, particularly if large angles exist between spherical signal points associated to neighboring graph vertices. No solution to this problem is known in the prior art.
The vertex position signals of polygon meshes used in computer aided geometric design, geometric modeling, medical imaging, and computer graphics to represent surfaces in digital form are usually three-dimensional, because these polygon meshes are used to approximate smooth surfaces embedded in three-dimensional space, rather than the planar two dimensional regions used in the mesh generation applications. In addition, these polygon meshes very often do not have boundaries. In these cases the Laplacian smoothing algorithm is applied without constraints, where all the output graph signal points are computed as the sum of the corresponding input signal points plus the product of a smoothing parameter times the corresponding Laplacian displacements. Sometimes the smoothing parameter is not explicitly referred to because it is embedded in the neighbor weights used to compute the Laplacian displacements. When Laplacian smoothing is applied to a noisy vertex position signal of a polygon mesh without constraints, noise is removed, but significant shape distortion may be introduced, caused mainly by two problems: shrinkage and tangential drift.
When a large number of Laplacian smoothing steps are iteratively performed with the same smoothing parameter, the shape undergoes significant deformations, eventually converging to the centroid of the original data. This problem is also called “shrinkage”. A simple modification to the Laplacian smoothing algorithm that solves the shrinkage problem, where the smoothing parameter alternates between a positive value and a negative value from iteration to iteration, is described in the paper “A Signal Processing Approach To Fair Surface Design,” by G. Taubin, Siggraph'95 Conference Proceedings, August 1995, pages 351-358, and in U.S. Pat. No. 5,506,947 “Curve and Surface Smoothing Without Shrinkage,” by G. Taubin. A number of other enhancements to Laplacian smoothing, introduced in recent years, are described in the paper “Geometric Signal Processing on Polygonal Meshes”, by G. Taubin, Eurographics 2000 State of The Art Report, September 2000,
Each Laplacian displacement produced by a Laplacian smoothing operator can be decomposed as the sum of two components, a tangential component and a normal component. Signal noise is contained in the normal component. When the lengths of the edges of a polygon mesh are not very uniform, the tangential components are not insignificant. The Laplacian displacements tend to make the lengths of the mesh edges more uniform. In addition to removing signal noise, the Laplacian smoothing algorithm may introduce significant tangential displacements. In some applications, such as when polygon meshes have associated textures mapped on them, this becomes a problem. To overcome this problem, referred to as the “tangential drift” problem, several modifications have been proposed in the prior art based on redefined non-linear Laplacian operators, where the neighbor weights are computed as function of the data. As mentioned above, non-linear Laplacian operators are undesirable because of the additional computational cost, and potential computational instabilities, which are difficult to analyze and predict. No solution to the tangential drift problem is known in the prior art based on linear Laplacian operators.
The ability to impose constraints to the smoothing process, such as specifying the position of some vertices, values of some normal vectors, the topology and geometry of ridge curves, or the behavior of the smoothing process along the boundaries of the mesh, is needed in the context of freeform interactive shape design. In the Laplacian smoothing algorithm and its linear derivatives, imposing interpolatory vertex position constraints is easy, but imposing interpolatory normal constraints is not. There is no solution to the problem of simultaneously imposing vertex positions and face normal constraints in the prior art based on a linear Laplacian operator.